/**
 * 1039. 多边形三角剖分的最低得分
 */
public class No1039 {
    private int[] values;

    /**
     * 1. 递归
     */
    public int minScoreTriangulation1(int[] values) {
        this.values = values;
        int n = values.length;
        return dfs(0, n - 1);
    }

    private int dfs(int i, int j) {
        if (i == j - 1) return 0;
        int res = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; k++) {
            res = Math.min(res, dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k]);
        }
        return res;
    }

    /**
     * 2. 迭代
     */
    public int minScoreTriangulation2(int[] values) {
        int n = values.length;
        int[][] f = new int[n][n];
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                f[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        return f[0][n - 1];
    }
}
